package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/
 * @Author: haogege
 * @Date: 2021/9/16
 */
public class _123_买卖股票的最佳时机III {

    public static void main(String[] args) {

        _123_买卖股票的最佳时机III iii = new _123_买卖股票的最佳时机III();

        int[] ins = {3,3,5,0,0,3,1,4};
        System.out.println(iii.maxProfit(ins));
    }

    public int maxProfit(int[] prices) {
        if (prices.length == 1) return 0;
        // 最多只能进行两笔交易，所以可以装换为寻找2比数据差值最大的
        int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < prices.length; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 -prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }

    public int maxProfit3(int[] prices) {
        if (prices.length == 1) return 0;
        // 定义4个状态
        int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;

        for (int i = 1; i < prices.length; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }

    // 超时 --> pass
    public int maxProfit1(int[] prices) {
        if (prices.length == 1) return 0;
        int max = 0;
        int[] splitAry = new int[prices.length];
        int splitIndex = 0;
        // 查找分割数组
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < prices[i - 1]) {
                splitAry[splitIndex++] = i;
            }
        }
        // 遍历分割数组
        for (int i = 0; i < splitIndex; i++) {
            max = Math.max(max, maxProfit(prices, 0, splitAry[i]) + maxProfit(prices, splitAry[i], prices.length));
        }
        return splitIndex == 0? prices[prices.length - 1] - prices[0]: max;
    }

    // 左闭着右开, 当前区间售卖一直股票的最大价值
    public int maxProfit(int[] prices, int begin, int end) {
        int min = prices[begin];
        int max = 0;
        for (int i = begin + 1; i < end; i++) {
            if (prices[i] > min) {
                max = Math.max(max, prices[i] - min);
            }
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}
